package com.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BinarySearch
{
    public static void main(String[] args)
    {
        int a[] = new int[]{-1, 0, 1, 2, -1, -4, 2, 3};
//        System.out.println(getPos(a, 5, 5));
        System.out.println(threeSum(null));
    }

    public static ArrayList<ArrayList<Integer>> threeSum(int[] num)
    {
        List<List<Integer>> list = new ArrayList<>();
        int len = num.length;
        if (len == 0 || len < 3)
        {
            return (ArrayList) list;
        }
        Arrays.sort(num);
        for (int i = 0; i < len; i++)
        {
            if (num[i] > 0)
            {
                break;
            }
            if (i > 0 && num[i] == num[i - 1])
            {
                continue;
            }
            int L = i + 1;
            int R = len - 1;
            while (L < R)
            {
                int sum = num[i] + num[L] + num[R];
                if (sum == 0)
                {
                    list.add(Arrays.asList(num[i], num[L], num[R]));
                    while (L < R && num[L] == num[L + 1]) L++;
                    while (L < R && num[R] == num[R - 1]) R--;
                    L++;
                    R--;
                }
                else if (sum < 0)
                {
                    L++;
                }
                else if (sum > 0)
                {
                    R--;
                }
            }
        }
        return (ArrayList) list;
    }

    public static ArrayList<ArrayList<Integer>> threeSum02(int[] num) {
        ArrayList<ArrayList<Integer>> results = new ArrayList<>();
        if(num==null||num.length<3){
            return results;
        }
        Arrays.sort(num);
        for (int i = 0; i < num.length; i++) {
            if (i != 0 && num[i] == num[i - 1]) {
                continue;
            }
            int num3 = num[i];
            int start = i + 1;
            int end = num.length - 1;
            while (start < end) {
                int num1 = num[start];
                int num2 = num[end];

                int count = num1 + num2 + num3;
                if (count > 0) {
                    end--;
                } else if (count < 0) {
                    start++;
                } else {
                    ArrayList result = new ArrayList();
                    result.add(num3);
                    result.add(num1);
                    result.add(num2);
                    results.add(result);
                    start++;
                    while(start<end&&num[start]==num[start-1]){
                        start++;
                    }
                }
            }

        }
        return results;
    }

}
